package kyssion.leetcode.num51_100;


import kyssion.leetcode.util.ShowUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * <p>
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * <p>
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * <p>
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * <p>
 * 说明:
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 * 示例:
 * <p>
 * 输入:
 * words = ["This", "is", "an", "example", "of", "text", "justification."]
 * maxWidth = 16
 * 输出:
 * [
 * "This    is    an",
 * "example  of text",
 * "justification.  "
 * ]
 * 示例 2:
 * <p>
 * 输入:
 * words = ["What","must","be","acknowledgment","shall","be"]
 * maxWidth = 16
 * 输出:
 * [
 * "What   must   be",
 * "acknowledgment  ",
 * "shall be        "
 * ]
 * 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
 * 因为最后一行应为左对齐，而不是左右两端对齐。
 * 第二行同样为左对齐，这是因为这行只包含一个单词。
 * 示例 3:
 * <p>
 * 输入:
 * words = ["Science","is","what","we","understand","well","enough","to","explain",
 * "to","a","computer.","Art","is","everything","else","we","do"]
 * maxWidth = 20
 * 输出:
 * [
 * "Science  is  what we",
 * "understand      well",
 * "enough to explain to",
 * "a  computer.  Art is",
 * "everything  else  we",
 * "do                  "
 * ]
 */
public class code68_文本左右对齐 {

    public static void main(String[] args) {
        List<String> list = new code68_文本左右对齐().fullJustify(
                new String[]{
                        "Science", "is", "what", "we", "understand", "well", "enough", "to", "explain",
                        "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do", "Science  is  what we"
                }, 20
        );
        ShowUtil.showList(list, true);
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        String[] needItem = new String[words.length];
        int index = 0;
        int length = 0;
        List<String> list = new ArrayList<>();
        for (int a = 0; a < words.length; a++) {
            if (index == 0) {
                length += words[a].length();
            } else {
                length += words[a].length() + 1;
            }
            if (length <= maxWidth) {
                needItem[index] = words[a];
                index++;
            } else {
                if (index == 0) {
                    return new ArrayList<>();
                }
                String newString = createLine(needItem, index, maxWidth);
                list.add(newString);
                index = 0;
                length = 0;
                a--;
            }
        }
        if (index > 0) {
            StringBuilder s = new StringBuilder();
            length = 0;
            for (int a = 0; a < index; a++) {
                if (a == 0) {
                    s.append(needItem[a]);
                    length+=needItem[a].length();
                } else {
                    s.append(" ").append(needItem[a]);
                    length+=needItem[a].length()+1;
                }
            }
            s.append(createK(maxWidth-length));
            list.add(s.toString());
        }
        return list;
    }

    private String createLine(String[] needItem, int index, int maxWidth) {
        int length = 0;
        for (int a = 0; a < index; a++) {
            length = length + needItem[a].length();
        }
        if (index == 1) {
            return needItem[0] + createK(maxWidth - needItem[0].length());
        }
        int base = (maxWidth - length) / (index - 1);
        int up = (maxWidth - length) - base * (index - 1);
        StringBuilder stringBuilder = new StringBuilder();
        for (int a = 0; a < index; a++) {
            if (a == 0) {
                stringBuilder.append(needItem[a]);
            } else {
                int o = up > 0 ? 1 : 0;
                stringBuilder.append(createK(base+o)).append(needItem[a]);
                if (up > 0) {
                    up--;
                }
            }
        }
        return stringBuilder.toString();
    }

    private String createK(int index) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int a = 0; a < index; a++) {
            stringBuilder.append(" ");
        }
        return stringBuilder.toString();
    }


    public List<String> fullJustify2(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int index = 0;
        while(index < words.length){
            int cur = index;
            int cur_row_len = words[index].length();
            index++;
            while(index < words.length){
                if(cur_row_len + words[index].length()+1 > maxWidth){
                    break;
                }
                cur_row_len += words[index].length()+1;
                index++;
            }
            StringBuilder sb = new StringBuilder();
            //先考虑最后一行的情况
            if(index == words.length){
                for(int i = cur;i < index;i++){
                    sb.append(words[i]+" ");
                }
                sb.deleteCharAt(sb.length() - 1);
                for(int i = sb.length();i < maxWidth;i++){
                    sb.append(" ");
                }
                res.add(sb.toString());
                break;
            }
            //all_word_len:所有单词的长度
            int all_word_len = 0;
            for(int i = cur;i<index;i++){
                all_word_len += words[i].length();
            }
            //space_num:至少空格的个数(为单词的个数-1,也就是中间的空缺部分)
            int space_num = index-cur-1;
            //remain_space:需要插入的空格个数
            int remain_space = maxWidth-all_word_len;
            int a = 0;
            int b = 0;
            if(space_num != 0){
                a = remain_space/space_num;
                b = remain_space%space_num;
            }
            for (int j = cur; j < index; j++) {
                if (sb.length() > 0) {
                    for (int k = 0; k < a; k++) {
                        sb.append(" ");
                    }
                    if (b != 0) {
                        sb.append(" ");
                        b--;
                    }
                }
                sb.append(words[j]);
            }
            for (int j = sb.length(); j < maxWidth; j++) {
                sb.append(" ");
            }
            res.add(sb.toString());
        }
        return res;
    }

}
